BOJ_1463_1로 만들기

DP(Dynamic Programming)의 기본 문제

3으로 나눠질 때, 2로 나눠질 때, 직전에서 1을 더할 때를 비교하여 가장 작은 값을 dp 배열에 넣어주면 된다

for문을 사용하여 1일 때부터 X일 때까지 값을 기록하며 올라갔다

dp[0], dp[1]은 계산을 위해 0을 넣어주었고, 나머지는 Integer.MAX_VALUE로 초기화해 주었다

package BJO;  
  
import java.util.Arrays;  
import java.util.Scanner;  
  
public class BJO_1463_1로만들기_다시풀기 {  
  
    public static void main(String[] args) {  
       Scanner scan = new Scanner(System.in);  
       int X = scan.nextInt();  
       int[] dp = new int[X + 1];  
       Arrays.fill(dp, Integer.MAX_VALUE);  
       dp[0] = 0;  
       dp[1] = 0;  
  
       for (int i = 1; i <= X; i++) {  
          dp[i] = Math.min(dp[i - 1] + 1, dp[i]);  
  
          if (i % 3 == 0) {  
             dp[i] = Math.min(dp[i / 3] + 1, dp[i]);  
          }  
  
          if (i % 2 == 0) {  
             dp[i] = Math.min(dp[i / 2] + 1, dp[i]);  
          }  
       }  
  
       System.out.println(dp[X]);  
    }  
}

#dp